BM13 判断一个链表是否为回文结构
https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
快慢指针的简单做法
其实快慢指针的做法和最下面的暴力解法差不多,只不过这里是用快慢指针来找到中间节点,然后再判断是否为回文结构
func isPail(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
count, pre := 0, head
for pre != nil {
count++
pre = pre.Next
}
var tmp []int
// 快慢指针
fast, low := head, head
for fast != nil && fast.Next != nil {
tmp = append(tmp, low.Val)
low = low.Next
fast = fast.Next.Next
}
if (len(tmp) * 2) < count {
low = low.Next
}
for i := len(tmp) - 1; i >= 0; i-- {
if low == nil || low.Val != tmp[i] {
return false
}
low = low.Next
}
return true
}
更优雅的做法:
func isPail(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
var nums []int
for head != nil {
nums = append(nums, head.Val)
head = head.Next
}
i, j := 0, len(nums)-1
for i < j {
if nums[i] != nums[j] {
return false
}
i++
j--
}
return true
}
暴力解法
直接把链表的值复制到数组中,然后用双指针判断是否为回文结构
func isPail(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
end, size := head, 0
for end != nil {
size++
end = end.Next
}
end = head
middle := size / 2
var leftArr, rightArr []int
for i := 0; i < size; i++ {
if i < middle {
leftArr = append(leftArr, end.Val)
} else {
rightArr = append(rightArr, end.Val)
}
end = end.Next
}
for i := range leftArr {
// 这里的 size%2 是为了偶数加一
if leftArr[i] != rightArr[middle-i-1+size%2] {
return false
}
}
return true
}